// 编写一个函数，检查输入的链表是否是回文的。

//  

// 示例 1：

// 输入： 1->2
// 输出： false 
// 示例 2：

// 输入： 1->2->2->1
// 输出： true 
//  

// 进阶：
// 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

#include "stdc++.h"

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

/* 栈
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> s{};
        ListNode* p{head};
        while (p) {
            s.push(p->val);
            p = p->next;
        }
        ListNode* q{head};
        while (q) {
            if (q->val != s.top()) {
                return false;
            }
            q = q->next;
            s.pop();
        }
        return true;
    }
};

/* 翻转一半链表 + 快慢指针
时间复杂度：O(n)
空间复杂度：O(1)
*/
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow{head};
        ListNode* fast{head};
        ListNode* pre{nullptr};
        // 同时进行翻转链表操作
        // 此循环结束后原链表被分成两段，两段的头分别是prev和slow
        while (fast && fast->next) {
            fast = fast->next->next;
            ListNode* temp = slow->next;
            slow->next = pre;
            pre = slow;
            slow = temp;
        }
        // 当长度为2n+1时，循环后fast为最后一个元素，slow为第n+1个元素，起始比较点从slow->next开始（第n+2个元素）。
        // 当长度为2n时，循环后fast为NULL，slow为第n+1个元素，起始比较点从slow开始，故不操作
        if (fast) {
            slow = slow->next;
        }
        while (pre && slow) {
            if (pre->val != slow->val) {
                return false;
            }
            pre = pre->next;
            slow = slow->next;
        }
        return true;
    }
};